Aller au contenu

16 Exos Algorithmes gloutons

Exercice 1⚓︎

  1. Programmer l’algorithme suivanten Python puis le tester sur la liste d’objets (vous pouvez compléter la trame proposée ci-dessous). On décide ici d'utiliser les listes ['nom', valeur, poids] pour représenter les objets. On pourrait aussi utiliser des dictionnaires...

    • Calculer les rapports valeur/poids de chaque objet et, dans la liste, ajouter ce rapport à chaque objet.
    • Trier la liste par ordre décroissant de rapports.
    • Parcourir tous les éléments de la liste et ajouter au sac à dos ceux dont le poids, cumulé au poids des objets déjà dans le sac, est inférieur ou égal à la capacité totale du sac.
    • Lorsque la capacité totale est dépassée, cela signifie, soit que le sac est plein, soit que l’objet est trop lourd pour être inséré intégralement dans le sac.
    • Dans ce dernier cas, ajouter la fraction de l’objet nécessaire pour atteindre la capacité maximale du sac.
    • Retourner la liste finale des objets se trouvant dans le sac ainsi que la valeur totale de ces objets.

  2. Comment être sûr que ce programme termine ?

  3. Déterminer le nombre d'opérations maximal nécessaire pour résoudre ce problème pour \(n\) objets (c'est la complexité temporelle de ce programme).
  4. Déterminer la place nécessaire en mémoire pour résoudre ce problème pour \(n\) objets (c'est la complexité en mémoire de ce programme).
🐍 Script Python
def sac_a_dos_frac(poidsmax, objets):
    """
    Cette fonction renvoie la liste des objets correspondant à la valeur maximale
    et ne dépassant pas le poids maximal que peut supporter le sac.
    Paramètres :
        poidsmax (int ou float) : le poids maximal que peut supporter le sac à dos
        objets : une liste d'objets
            chaque objet est un dictionnaire, avec un nom, une valeur, une masse
    Renvoie :
        la liste des objets dérobés par le voleur
        et la valeur totale correspondante 
    """    
    assert type(poidsmax) == int or type(poidsmax) == float, "Le poids maximal du sac à dos doit être un nombre"
    assert type(objets) == list, "Entrer les objets sous forme d'une liste de dictionnaires [['nom': objet 1, 'valeur': valeur1, 'masse': poids1], etc]"

    # on fait une copie de la liste d'objets pour ne pas modifier la liste d'origine
    objets_copie = objets.copy()

    # on calcule le rapport (valeur/poids) pour chaque objet et on met à jour la liste d'objets en lui ajoutant cette nouvelle donnée 'rapport'
    for objet in objets_copie:
        #... À compléter
        objet['rapport'] = rapport

    # on range cette liste par ordre décroissant des rapports
    objets_copie.sort(key = lambda x: x['rapport'], reverse = True)

    # on initialise trois variables
    masse_actuelle = 0 # représente la masse du sac après insertion d'un nouvel objet
    valeur_actuelle = 0 # représente la valeur contenue dans le sac après insertion d'un nouvel objet
    solution = [] # représente la liste des objets insérés dans le sac

    # on parcourt un par un les objets de la liste triée
    for objet in objets_copie:
        if masse_actuelle + objet['masse'] <= poidsmax: # on teste si le nouvel objet a une masse lui permettant d'être inséré dans le sac à dos
            #... À compléter # si c'est le cas, on met à jour la masse du sac
            #... À compléter # on met à jour la valeur totale
            #... À compléter # et on l'insère dans le sac
        else: # la masse du nouvel objet dépasse la masse encore disponible : on va en prendre une fraction pour atteindre exactement la masse maximale du sac
            masse_frac_dernier_objet = #... À compléter
            valeur_frac_dernier_objet = #... À compléter
            valeur_actuelle += #... À compléter
            masse_actuelle += #... À compléter
            solution.append({'nom': f"{(poidsmax - masse_actuelle) / objet['masse']} de {objet['nom']}", 'valeur': valeur_frac_dernier_objet, 'masse': masse_frac_dernier_objet, 'rapport': objet['rapport']})
        # Si le sac à dos est plein, on ne passe pas à l'objet suivant, on retourne le résultat immédiatement
        if masse_actuelle == poidsmax:
            return solution, valeur_actuelle

    # on renvoie la liste des objets dérobés par le voleur et la valeur totale correspondante
    return solution, valeur_actuelle


# Testons notre fonction sur l'exemple du cours
p = 30
OBJETS = [{"nom": "A", "valeur": 700, "masse": 13},
          {"nom": "B", "valeur": 400, "masse": 12},
          {"nom": "C", "valeur": 300, "masse": 6},
          {"nom": "D", "valeur": 300, "masse": 10},
          {"nom": "E", "valeur": 500, "masse": 12},
          {"nom": "F", "valeur": 200, "masse": 14}]
objets_derobes, valeur_derobee = sac_a_dos_frac(p, OBJETS)
print("La liste des objets dérobés est la suivante : \n" + str(objets_derobes))
print("Pour une valeur total de : " + "{:,}".format(valeur_derobee).replace(',', ' ') + " euros.")

Exercice 2⚓︎

  1. Adapter le programme ci-dessus à la variante entière du problème du sac à dos (on pourra compléter la trame proposée ci-dessous).
  2. Quelle solution nous donne-t-il sur l’exemple précédent ?
  3. Le tester pour la liste d’objets [['A', 165, 3], ['B', 100, 2], ['C', 100, 2]] et un poids maximal de \(4\) kg. La solution renvoyée est-elle optimale ?
🐍 Script Python
def sac_a_dos_0_1(poidsmax, objets):

    for objet in objets:
       #... À compléter
       #... À compléter

    objets_copie.sort(key = lambda x: x['rapport'], reverse = True)

    masse_actuelle = 0 # représente la masse du sac après insertion d'un nouvel objet
    valeur_actuelle = 0 # représente la valeur contenue dans le sac après insertion d'un nouvel objet
    solution = [] # représente la liste des objets insérés dans le sac

    for objet in objets:
        if #... À compléter:
            #... À compléter
            #... À compléter
            #... À compléter

    return solution, valeur_actuelle

# Testons notre fonction sur l'exemple du cours
print("Exemple du cours : ")
p = 30
objets = [{"nom": "A", "valeur": 700, "masse": 13},
          {"nom": "B", "valeur": 400, "masse": 12},
          {"nom": "C", "valeur": 300, "masse": 6},
          {"nom": "D", "valeur": 300, "masse": 10},
          {"nom": "E", "valeur": 500, "masse": 12},
          {"nom": "F", "valeur": 200, "masse": 14}]
objets_derobes, valeur_derobee = sac_a_dos_0_1(p, objets)
print("La liste des objets dérobés est la suivante : \n" + str(objets_derobes))
print("Pour une valeur total de : " + "{:,}".format(valeur_derobee).replace(',', ' ') + " euros.")

# Testons notre fonction sur l'exemple de la question 3
print("Exemple de la question 3 : ")
p = 4
objets = [{'nom': 'A', 'valeur': 165, 'masse': 3},
          {'nom': 'B', 'valeur': 100, 'masse': 2}, 
          {'nom': 'C', 'valeur': 100, 'masse': 2}]
objets_derobes, valeur_derobee = sac_a_dos_0_1(p, objets)
print("La liste des objets dérobés est la suivante : \n" + str(objets_derobes))
print("Pour une valeur total de : " + "{:,}".format(valeur_derobee).replace(',', ' ') + " euros.")